The present invention relates to digital data communication systems, and is particularly directed to a new and improved arbitration mechanism for a statistically multiplexed frame relay switching system, which is effective to optimize allocation of a limited bandwidth aggregate data link among access lines that are coupled to respective ports of the frame relay switching system.
Frame relay (FR) switching systems currently enjoy widespread success for supplying digital data servicesxe2x80x94principally in support of local area network (LAN) integration across wide area facilities. Frame relay derives its benefit by multiplexing xe2x80x98framesxe2x80x99 of data, or packetized data traffic, from each of a plurality of physical circuits into a common or shared backbone network, so as to reduce overall transport requirements, by creating more efficient use of the available transport bandwidth.
Prior to the advent of frame relay switching systems, LAN integration required the purchase of point-to-point digital data services delivered via individual physical circuits. Among the advantages frame relay provides over point-to-point services are enhanced network reliability and troubleshooting, through redundant and highly manageable switching networks, multiple end-to-end connections via permanent virtual circuits (PVCs) over single physical interfaces, and lower deployment costs that often result in lower consumer fees.
Unfortunately, due to the sporadic nature of data, the efficient utilization of the available bandwidth of such physical interfaces is relatively low, considering the ratio of data transport time (during which the communication circuits are actually sending data over the network) to non-data or idle time (when the circuits are xe2x80x98waitingxe2x80x99 for an instruction initiated by the end user). This relatively low efficient utilization is due principally to a common attribute that is shared by a significant number of typical data networking applications (such as e-mail, web-browsing, terminal input, automatic teller machines, and credit card verification devices); much of the data traffic they generate is in response to some human intervention.
As a non-limiting example, when using a web browser, an end customer may download a magazine article from a web site; the user will then probably spend some period of time reading or at least skimming the article, before xe2x80x98surfingxe2x80x99 for something else. During the time interval that the user is reading the article, the available bandwidth of the data connection is essentially wasted, since no data is being transmitted. While this low utilization efficiency may not be significant in terms of a single dial-up customer, when multiplied by thousands of users, it results in a large number of bandwidth resources being utilized at far less than capacity. This low utilization of available bandwidth results from the necessity of back-hauling services from the communication service supplier (e.g., an internet service provider (ISP)) to the switching backbone.
In a typical implementation, rather than being dispersed throughout the network, the switching backbone is confined to a very limited geographic area, requiring significant back-haul support. In addition, in stark contrast to the widespread availability of central office voice switches, the number of available data switches is relatively small. Also, due to the nature of physical interface design, a frame relay switch is often not necessarily employed in a manner that makes full use of its frame processing functionality. By accessing the frame relay switch through point-to-point facilities, both data transport time and idle time are presented to the switch interface. The frame relay switch then becomes limited at the point of its physical port access, often mandating the purchase and installation of additional frame relay switches and line cards.
In order to better utilize frame relay switch capability, as well as increase the utilization of back-haul transport bandwidth, it is desirable to efficiently extend frame multiplexing to central offices, remote terminals (RTs) and customer premises equipment (CPE) environments in a manner that address current deployment schemes. For this purpose, it has been proposed to implement frame relay switching networks in an architecture of the type diagrammatically shown in FIG. 1.
In this architecture, a plurality of frame relay channel units (frameports) 11 terminate a large number of access lines 13 from associated CPEs 15, and are coupled to an aggregate data link 21 from the network 10. The aggregate data link has a data transport capacity that is considerably less than the cumulative data capacity of all of the access lines 13. Integrated into this architecture is a transport access mechanism that statistically multiplexes data from the various CPEs 15 into a single data stream for transport over the aggregate data link 21. The use of statistically multiplexing serves to reduce the back-hauling of circuits to the data switch, thereby more efficiently utilizing aggregate data transport resources, since the data is multiplexed at the point of access (the respective frame relay channel units 11), rather than at the switch.
In order to provide an orderly and efficient allocation of the limited bandwidth of the aggregate link 21 to each access line 13 requesting service, yet without allowing any individual access line to tie up the aggregate data link during periods of inactivity or congestion, the statistical multiplexing of data from the access lines to the aggregate data link is based upon a prescribed opportunity-to-transmit arbitration mechanism, that is distributed among all users of the system, so that the state of the system is effectively shared with each access line.
For this purpose, each frame relay channel unit 11 is coupled to a common (wire-ORed) arbitration link 12, that allows each channel unit to simultaneously share arbitration information, through which xe2x80x98ownershipxe2x80x99 of the aggregate data link 21 is allocated in accordance with a specified xe2x80x98right to transmitxe2x80x99 rule set.
In accordance with the present invention, there is provided a new and improved arbitration mechanism for controlling the manner in which data from a plurality of access lines, the cumulative bandwidth of which far exceeds that of the aggregate data link, is statistically multiplexed through a frame relay switching system of the type described above, by calculating for each data line an arbitration value based upon a combination of parameters, including queuing delay and information customized for the particular configuration and traffic rate of that line.
As will be described, the arbitration mechanism of the present invention enables user devices to readily interface with each other, in order to determine which device should have access to the aggregate data link, regardless of the degree of traffic congestion. The arbitration mechanism of the invention is able to accommodate periods of aggregate link congestion in a fair, orderly and predictable manner, that ensures that the oldest data packet awaiting transmission will not be excluded from gaining access to the aggregate data link to the benefit of initially higher priority class of service lines.
For this purpose, the control processor of each frame relay channel unit executes a statistical multiplexing arbitration routine, which calculates a respective arbitration value that forms part of the contents of a composite arbitration code presented to and readable by each frame relay channel unit, via a common physical medium (wire-ORed arbitration bus) during a respective arbitration cycle. The use of a common physical arbitration medium allows each participating channel unit to simultaneously share its arbitration code with all other channel units. Since arbitration cycles will occur: at a rate that is directly proportional to the flow of data into the network, they are not periodic and are asynchronous to other system events.
The channel units operate in a xe2x80x98pseudo-synchronousxe2x80x99 mode, performing sample and shift operations on their respectively generated arbitration values, one bit at a time, using a common clock, such as that used for the aggregate data stream. The wire-ORed arbitration bus is electrically configured such that a first logical state (e.g., xe2x80x981xe2x80x99), associated with an idle condition, corresponds to a high impedance state, and is pulled high by a pull-up resistor. The arbitration bit is driven low (e.g., logical xe2x80x980xe2x80x99) to a prescribed voltage level (e.g., zero volts), when a channel unit requests an arbitration cycle.
The format of the composite arbitration code includes a start bit, a (quasi unique) multibit calculated arbitration value code, and an address code that identifies the actual physical location of the respective channel unit. By quasi unique is meant that the contents of the calculated arbitration value code should, but may not necessarily, be unique for each channel unit. Uniqueness is due to the fact that the arbitration value code is calculated on the basis of a plurality of parameters that have a high probability of being different for each access line. Such parameters include quality of service, committed information rate, and a queuing age parameter that represents the length of time that has elapsed since the line of interest last received service (had ownership of the aggregate data link). As long as a requesting line (having at least one packet to send) is not given ownership of the link, the value of its queuing age will continue to be sequentially incremented.
The calculated arbitration value code is combined with the start bit and the address code to produce a composite arbitration code, which is asserted onto the arbitration bus. Each channel unit compares the sampled state of the start bit portion of the arbitration bus with the value of the start bit contained in the arbitration code that was asserted onto the arbitration bus by that channel unit. If the sampled state of the start bit portion of the bus differs from what was asserted, the channel unit ceases participation in the arbitration cycle and terminates assertion of its composite arbitration value code. However, if the sampled state of the start bit is the same as what it has asserted, the channel unit becomes an active participant in that portion of the arbitration cycle which awards the aggregate link to the highest priority participating line.
As each channel unit""s arbitration code is clocked onto the arbitration bus, a respective channel unit will perform a bit by bit comparison, for each bit that it sequentially clocks onto the bus, with the state of the bus as driven by other channel units, to determine whether that channel unit may be given priority to transmit. As bits are sequentially clocked onto the bus, whenever a channel unit sees a difference between its bit value and that on the bus, the channel unit knows it has a lower priority and terminates its participation in the arbitration cycle. As a result, at the end of the arbitration cycle (when all bits of the arbitration code have been clocked onto the arbitration bus), only the channel unit having the largest priority will not have dropped out, allowing it to take ownership of the aggregate data link. That channel unit then transmits its packet, and releases ownership of the link for reassignment at the next arbitration cycle.